/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "str.h"
#include "idx.h"
//---------------------------------------------------------------------------
static __inline__ void index_insert_key(
  struct index_link * link,
  uint32_t position,
  const void * key,
  const void * data,
  const byte_size_int * next_level_block_index)
{
  uintptr_t entry_size = link->idx->entries_sizes[link->blk->type];
  uint8_t * p = link->blk->keys + position * entry_size;

#if COMPILE_RUNTIME_CHECKS
  if( key == NULL ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( position > link->blk->count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  //if( link->blk->count > link->idx->blk_max_keys[link->blk->type] ){
  //  fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
  //  abort();
  //}
#endif

  memmove(p + entry_size,p,(link->blk->count - position) * entry_size);
  memcpy(p,key,link->idx->key_size);
  p += link->idx->key_size;

  if( link->blk->type == INDEX_LEAF ){
#if COMPILE_RUNTIME_CHECKS
    if( data == NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    memcpy(p,data,link->idx->data_size);
  }
  else if( link->blk->type == INDEX_NODE ){
#if COMPILE_RUNTIME_CHECKS
    if( next_level_block_index == NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    memcpy(p,next_level_block_index,link->idx->block_index_size);
    p += link->idx->block_index_size;
  }
  else {
    errno = EINVAL;
#if COMPILE_RUNTIME_CHECKS
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
#endif
    return;
  }

  link->blk->count++;
  if( position == 0 && !bsint_is_zero(&link->block_index,link->idx->block_index_size) )
    link->zero_position_changed = true;
}
//---------------------------------------------------------------------------
static __inline__ void scatter_block_in_mem(
  struct index * idx,
  struct index_link * link,
  struct index_link ** p_right)
{
  struct index_link * right;
  uintptr_t half = link->blk->count / 2;
#if COMPILE_RUNTIME_CHECKS
  uint8_t * entry;
#endif

  *p_right = right = index_link_new_v(idx->cache->block_size);
  right->idx = idx;
  right->blk->type = link->blk->type;
  right->blk->count = 0;
  memcpy(&right->blk->prev_block_index,&link->blk->prev_block_index,idx->block_index_size);
  index_cut_paste_keys(right,0,link,half,link->blk->count - half);
#if COMPILE_RUNTIME_CHECKS
  entry = index_block_entry(link,link->blk->count);
  memset(entry,0,(uint8_t *) link->blk + idx->cache->block_size - entry);
  entry = index_block_entry(right,right->blk->count);
  memset(entry,0,(uint8_t *) right->blk + idx->cache->block_size - entry);
#endif
}
//---------------------------------------------------------------------------
static void index_insert_entry(
  struct index * idx,
  struct index_btree_stack_entry * e,
  const void * key,
  const void * data,
  const byte_size_int * next_level_block_index)
{
  struct index_link * link = e->link;
  uintptr_t block_size = idx->cache->block_size;
  uint32_t max_keys = idx->blk_max_keys[link->blk->type];
  uint32_t count = link->blk->count / max_keys;

  if( count > 0 && link->blk->count % max_keys == 0 ){
    void * new_blk = salloc(block_size * (count + 1),NULL);
    if( new_blk == NULL ){
#if COMPILE_RUNTIME_CHECKS
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
#endif
      return;
    }
    memcpy(new_blk,link->blk,block_size * count);
#if COMPILE_RUNTIME_CHECKS
    memset((uint8_t *) new_blk + block_size * count,0,block_size);
#endif
    sfree(link->blk);
    link->blk = new_blk;
  }

  index_insert_key(link,e->insert_position,key,data,next_level_block_index);
  e->link_change = ILC_UPD;
}
//---------------------------------------------------------------------------
static void reset_prev(
  struct index * idx,
  struct index_link * link)
{
  uintptr_t i;
  const byte_size_int * block_index;
  struct index_link_change change;
  struct index_link * cur_link;

  if( link->blk->type == INDEX_NODE ){
    for( i = 0; i < link->blk->count; i++ ){
      block_index = index_block_link(link,i);
      cur_link = index_link_block(idx,block_index);
      if( errno != 0 ) return;

      memcpy(&cur_link->blk->prev_block_index,&link->block_index,idx->block_index_size);

      change.link = cur_link;
      change.what = ILC_UPD;
      array_lookup_insert_copy(&idx->changed_links,&change);
      
      mutex_acquire(&idx->cache->links_mutex);
      cur_link->linked--;
      mutex_release(&idx->cache->links_mutex);
    }
  }
}
//---------------------------------------------------------------------------
void index_scatter_block(struct index * idx,struct index_link * root,struct index_link * link)
{
  struct index_link_change change;
  struct index_btree_stack_entry e;
  struct index_link * right;
#ifndef NDEBUG
  static uintptr_t count = 0;
#endif
  uintptr_t block_size = idx->cache->block_size;
  uint32_t max_keys = idx->blk_max_keys[link->blk->type], max_keys2 = max_keys * 2;
#if COMPILE_RUNTIME_CHECKS
  uint8_t * entry;
#endif

  if( link->blk->count <= max_keys && !link->zero_position_changed ) return;

//#ifndef NDEBUG
//  idx->callbackf(idx->callback_object);
//#endif

  if( link == root ){
//#ifndef NDEBUG
//    idx->callbackf(idx->callback_object);
//#endif
#if COMPILE_RUNTIME_CHECKS
    if( link->zero_position_changed ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    right = index_link_new_v(block_size);
    right->idx = idx;
    right->blk->type = link->blk->type;
    right->blk->count = link->blk->count;
    index_block_allocate(idx,&right->block_index);
    index_link_block_n(idx,right);

    memxchg(&link->blk,&right->blk,sizeof(link->blk));

    link->blk->type = INDEX_NODE;
    link->blk->count = 1;

    memcpy(link->blk->keys,right->blk->keys,idx->key_size);
    memcpy(link->blk->keys + idx->key_size,&right->block_index,idx->block_index_size);

#if COMPILE_RUNTIME_CHECKS
    entry = index_block_entry(link,link->blk->count);
    memset(entry,0,(uint8_t *) link->blk + block_size - entry);
#endif

    change.link = right;
    change.what = ILC_NEW;
    array_lookup_insert_copy(&idx->changed_links,&change);

//#ifndef NDEBUG
//    idx->callbackf(idx->callback_object);
//#endif

    reset_prev(idx,right);

    link = right;
  }

  if( bsint_is_zero(&link->blk->prev_block_index,idx->block_index_size) ){
    e.link = root;
  }
  else {
    e.link = index_link_block(idx,&link->blk->prev_block_index);
    if( errno != 0 ) return;
  }

  if( link->zero_position_changed ){
    index_lookup_key(&e,link->blk->keys,0);
    memcpy(index_block_entry(e.link,e.next_level_position),link->blk->keys,idx->key_size);
    if( e.next_level_position == 0 && e.link != root ) e.link->zero_position_changed = true;
    link->zero_position_changed = false;
  }

  //if( bsint_get_be64toh(&link->block_index,idx->block_index_size) == 0x000015 ){
  //  DEBUG_index_dump_block_keys(stderr,e.link);
  //}
  //{
  //  uint32_t key = htobe32(0x000D42BC);
  //  intptr_t c = DEBUG_index_lookup_key(idx,root,&root->block_index,&key);
  //  if( c != 0 || count == 0x0 ){
  //    c = DEBUG_index_lookup_key_dump(idx,root,&root->block_index,&key);
  //  }
  //  count++;
  //}

  //if( count >= 0x0 ){
  //  fprintf(stderr,"\n");
  //  DEBUG_index_dump_block_keys_range(stderr,e.link);
  //  DEBUG_index_dump_block_keys_range(stderr,link);
  //}

  index_lookup_key(&e,link->blk->keys,0);
#if COMPILE_RUNTIME_CHECKS
  if( e.c != 0 ){
    DEBUG_index_dump_block_keys(stderr,e.link);
    DEBUG_index_dump_block_keys(stderr,link);
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif
  e.insert_position++;

  while( link->blk->count > max_keys ){
    uint32_t cut_keys = link->blk->count < max_keys2 ? link->blk->count / 2 : max_keys;

    right = index_link_new_v(block_size);
    right->idx = idx;
    right->blk->type = link->blk->type;
    memcpy(&right->blk->prev_block_index,&link->blk->prev_block_index,idx->block_index_size);
    index_block_allocate(idx,&right->block_index);
    index_link_block_n(idx,right);
    index_cut_paste_keys(right,0,link,link->blk->count - cut_keys,cut_keys);

    //if( count >= 0x0 ){
    //  DEBUG_index_dump_block_keys_range(stderr,right);
    //  DEBUG_index_dump_block_keys(stderr,e.link);
    //}

    index_insert_entry(idx,&e,right->blk->keys,NULL,&right->block_index);

    change.link = right;
    change.what = ILC_NEW;
    array_lookup_insert_copy(&idx->changed_links,&change);

    //if( count >= 0x0 ){
    //  DEBUG_index_dump_block_keys(stderr,e.link);
    //}
    reset_prev(idx,right);
  }

  link->blk = salloc(block_size,link->blk);
#if COMPILE_RUNTIME_CHECKS
  entry = index_block_entry(link,link->blk->count);
  memset(entry,0,(uint8_t *) link->blk + block_size - entry);
#endif

  //if( count >= 0x0 ){
  //  DEBUG_index_dump_block_keys_range(stderr,e.link);
  //  DEBUG_index_dump_block_keys_range(stderr,link);
  //}

  //{
  //  uint32_t key = htobe32(0x000D42BC);
  //  intptr_t c = DEBUG_index_lookup_key(idx,root,&root->block_index,&key);
  //  if( c != 0 ){
  //    c = DEBUG_index_lookup_key_dump(idx,root,&root->block_index,&key);
  //  }
  //}

  change.link = e.link;
  change.what = ILC_UPD;

  array_lookup_insert_copy(&idx->changed_links,&change);

  //if( e.link->zero_position_changed || e.link->links.count > 0 )
  //  array_lookup_insert_copy(new_changed_links,&change);
  
  index_scatter_block(idx,root,e.link);

//#ifndef NDEBUG
//  idx->callbackf(idx->callback_object);
//#endif

  if( e.link != root ){
    mutex_acquire(&idx->cache->links_mutex);
    e.link->linked--;
    mutex_release(&idx->cache->links_mutex);
  }
}
//---------------------------------------------------------------------------
//static void scatter_block(
//  struct index * idx,
//  struct index_btree_stack_entry * e)
//{
//  uintptr_t half = e->link->blk->count / 2;
//  byte_size_int * new_block_index = alloca(idx->block_index_size);
//
//  bool root = bsint_is_zero(&e->link->block_index,idx->block_index_size);
//
//  if( root ){
//    index_block_allocate(idx,new_block_index);
//    e->left = index_link_block_noread(idx,new_block_index);
//    e->left->blk->type = e->link->blk->type;
//    e->left->blk->count = 0;
//#if COMPILE_RUNTIME_CHECKS
//    memset(e->left->blk->keys,0,
//      idx->blk_max_keys[e->left->blk->type]
//        * idx->entries_sizes[e->left->blk->type]);
//#endif
//    //rwlock_acquire_write_lock(&e->left->lock);
//    //e->left_lock = RWL_WRITE;
//  }
//
//  index_block_allocate(idx,new_block_index);
//  e->right = index_link_block_noread(idx,new_block_index);
//  e->right->blk->type = e->link->blk->type;
//  e->right->blk->count = 0;
//#if COMPILE_RUNTIME_CHECKS
//  memset(e->right->blk->keys,0,
//    idx->blk_max_keys[e->right->blk->type]
//      * idx->entries_sizes[e->right->blk->type]);
//#endif
//  //rwlock_acquire_write_lock(&e->right->lock);
//  //e->right_lock = RWL_WRITE;
//
//  if( root ){
//
//    index_cut_paste_keys(e->right,0,e->link,half,e->link->blk->count - half);
//    index_cut_paste_keys(e->left,0,e->link,0,e->link->blk->count);
//
//    if( e->link->blk->type == INDEX_LEAF ) e->link->blk->type = INDEX_NODE;
//
//    index_insert_key(e->link,0,index_block_entry(e->left,0),NULL,&e->left->block_index);
//    index_insert_key(e->link,1,index_block_entry(e->right,0),NULL,&e->right->block_index);
//
//    e->left_change = ILC_NEW;
//  }
//  else {
//    index_cut_paste_keys(e->right,0,e->link,half,e->link->blk->count - half);
//  }
//
//  e->link_change = ILC_UPD;
//  e->right_change = ILC_NEW;
//}
//---------------------------------------------------------------------------
void index_scatter(
  struct index * idx,
  struct index_btree_stack * stack,
  const void * key,
  const void * data)
{
  int err = EEXIST;
  struct index_btree_stack_entry * e;
  
  index_get_key_path(idx,stack,key,0);

  e = array_get(&stack->entries,stack->sp);

  if( errno != 0 ){
    err = errno;
  }
  else if( e->c != 0 ){
    rwlock_acquire_read_lock(&idx->changed_links_lock);

    rwlock_upgrade(&e->link->lock);
    e->link_lock = RWL_WRITE;

    index_insert_entry(idx,e,key,data,NULL);

    err = 0;

    rwlock_upgrade(&idx->changed_links_lock);
    index_unwind_stack(idx,stack,RWL_NONE);
    rwlock_release_write_lock(&idx->changed_links_lock);
  }
  errno = err;
}
//---------------------------------------------------------------------------
